package com.leetcode.knapsack;

/**
 * 自顶向下  0-1背包问题
 * <p>
 * F(i,C)=max(F(i−1,C),v(i)+F(i−1,C−w(i)))
 */
public class KnapsackV1 {

    private int[][] memo;

    public int solveKS(int[] w, int[] v, int C) {
        int size = w.length;
        memo = new int[size][C + 1];
        return solveKS(w, v, size - 1, C);
    }

    /**
     * 解决背包问题的递归函数
     *
     * @param w        物品的重量数组
     * @param v        物品的价值数组
     * @param index    当前待选择的物品索引
     * @param capacity 当前背包有效容量
     * @return 最大价值
     */
    private int solveKS(int[] w, int[] v, int index, int capacity) {
        if (index < 0 || capacity <= 0) {
            return 0;
        }

        //如果此子问题已经求解过，则直接返回上次求解的结果
        if (memo[index][capacity] != 0) {
            return memo[index][capacity];
        }

        //不放index个物品的所得价值
        int res = solveKS(w, v, index - 1, capacity);

        //放index个物品所得价值(前提是能放的下)
        if (w[index] <= capacity) {
            res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
        }

        //添加子问题的解，便于下次直接使用
        memo[index][capacity] = res;

        return res;
    }

    public static void main(String[] args) {
        KnapsackV1 testKnapsackV1 = new KnapsackV1();

        int[] w = {2, 1, 3, 2};
        int[] v = {12, 10, 20, 15};

        System.out.println(testKnapsackV1.solveKS(w, v, 5));
    }

}
